/**
 * 项目名称: prim.cpp
 * 项目路径: study/DataStructure/数据结构/图/应用/最小生成树
 * 编辑时间: 2024年08月10日10时00分39秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

/**
 * prim算法:从某一个顶点开始构建生成树,每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止
 * @return
 */
const int N =510;

int n;//表示顶点数
int g[N][N];//邻接矩阵,存储所有边
int dist[N];//存储其他点到当前最小生成树的距离
bool st[N];//存储每个点是否已经在生成树中

int prim(){
    memset(dist,0x3f, sizeof dist);
    dist[1]=0;//一号点到最小生成树的距离为0
    int res = 0;//代价
    for(int i=1;i<=n;i++){
        int t= -1;
        //循环找到与生成树相连顶底中代价最小的顶点
        for(int j =1;j<=n;j++){
            if(!st[j] && (t==-1 || dist[t]>dist[j]))
                t=j;
        }
        //表明该图是一个未连通图,不可能存在最小生成树
        if(dist[t] == 0x3f3f3f3f)return 0x3f3f3f3f;
        res+=dist[t];
        st[t]=true;//此点已加入最小生成树
        //更新当前生成树到其他点的最小代价
        for(int j =1;j<=n;j++)dist[j] = min(dist[j],g[t][j]);
    }
    return res;
}

int main() {

    return 0;
}
